package com.LeeCode;

import java.util.*;

/**
 * 链表中的下一个更大节点
 */

public class Code1019 {
    public static void main(String[] args) {
        int[] arr = {2, 7, 4, 3, 5};
        ListNode head = Utils.arrayToListNode(arr);
        System.out.println(Arrays.toString(new Code1019().nextLargerNodes1(head)));
    }

    public int[] nextLargerNodes(ListNode head) {
        // Step 1: 转换成数组
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        int n = list.size();
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        // Step 2: 从后往前遍历 + 单调栈
        for (int i = n - 1; i >= 0; i--) {
            int val = list.get(i);

            // 弹出所有 <= 当前值的元素
            while (!stack.isEmpty() && stack.peek() <= val) {
                stack.pop();
            }

            // 栈顶即为下一个更大元素
            res[i] = stack.isEmpty() ? 0 : stack.peek();

            // 把当前值压入栈
            stack.push(val);
        }

        return res;
    }

    public int[] nextLargerNodes1(ListNode head) {
        ListNode cur = head, prev = null;
        int n = 0;
        while (cur != null) {
            n++;
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        int[] ans = new int[n];
        cur = prev;

        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= cur.val) {
                stack.pop();
            }
            ans[i] = stack.isEmpty() ? 0 : stack.peek();
            stack.push(cur.val);
            cur = cur.next;
        }

        return ans;
    }
}
